package com.yu1996.Algorithm.Sorting;


import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/**
 * @Description: 插入排序   从第二个位置开始   依次和前面的数进行比较  找出插入的位置   总结：80000随机数的执行时间大约1秒
 * @author: xing
 * @Date: 2019/8/15 9:45
 */
public class InsertSort {

    public static void main(String[] args) {

        //定义数组
//        int[] arr = {8, 6, 9, 2, -1};
        //测试插入排序
//        insertSort(arr);
        int[] arr = new int[80000];
        for (int i = 0; i < 80000; i++) {
            arr[i] = (int) (Math.random() * 80000);
        }

        //测试冒泡排序所需时间
        Date date1 = new Date();
        SimpleDateFormat dateFormat = new SimpleDateFormat("yyyy-mm-dd  hh:mm:ss");
        String date1Str = dateFormat.format(date1);
        System.out.println(date1Str);
        //测试冒泡排序
        insertSort(arr);
        Date date2 = new Date();
        String date2Str = dateFormat.format(date2);
        System.out.println(date2Str);
    }


    public static void insertSort(int[] arr) {

        for (int i = 1; i < arr.length; i++) {
            int insertVal = arr[i];
            int insertSel = i - 1;
            while (insertSel >= 0 && arr[insertSel] > insertVal) {
                //表示找到当前数插入的位置  将找到位置之后的元素全部后移
                arr[insertSel + 1] = arr[insertSel];
                insertSel--;
            }
            //循环结束表示  已将位置找到并且位置都已移动完成   直接插入即可
            arr[insertSel + 1] = insertVal;
//            System.out.println("第" + i + "次循环：");
//            System.out.println(Arrays.toString(arr));
        }
    }
}
